package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021-04-07 22:16
 * @Version 1.0
 * 可以理解为从数组前面截取一部分，然后放到后面去，强行将一个有序的数组变成两段有序的数组，然后查找一个值是否在数组里。
 * 所以就用旋转后的数组*2（复制放到后面），其子数组包含原数组，原数组是有序的，可以用二分查找。
 *
 * 考察点：分片二分查找
 **/
public class SearchInRotatedSortedArrayII {


    /**
     * 暴力遍历，检查到相等的就返回
     * @param nums
     * @param target
     * @return
     */
    public boolean search(int[] nums, int target) {
        boolean result = false;
        for (int num : nums) {
            if (target == num) {
                result = true;
                break;
            }
        }
        return result;
    }

    /**
     * 预检查，之后再在段内暴力查找
     * @param nums
     * @param target
     * @return
     */
    public boolean search2(int[] nums, int target) {
        int len = nums.length;
        int tag = 0;
        boolean result = false;
        if (nums[tag] == target) {
            result = true;
        } else if (nums[tag] > target) {
            for (int i = len-1; i >= 0; i--) {
                if (nums[i] == target) {
                    result = true;
                    break;
                }
                if (i < len -1 && nums[i] > nums[i+1]) {
                    break;
                }
            }
        } else {
            for (int i = 1; i < len; i++) {
                if (nums[i] == target) {
                    result = true;
                    break;
                }
                if (nums[i] < nums[i-1]) {
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 3. 先查找到断点再分别二分查找
     */
}
